home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 9479 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Best Binary Search Tree Balance Algo?
  5. Date: 10 Mar 1996 13:15:57 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4hvgqdINN598@keats.ugrad.cs.ubc.ca>
  8. References: <4hqvc5$p9k@solaria.cc.gatech.edu>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4hqvc5$p9k@solaria.cc.gatech.edu>,
  12. David Mitchell <bigdave@cc.gatech.edu> wrote:
  13. >I would like to know what the run-time of the best binary search tree 
  14. >balance algorithm is.  (e.g. O(n^2), O(n lg n), etc.).
  15.  
  16. This question needs a lot more qualification. First of all, algorithms which
  17. balance trees (Red-Black, AVL) do so incrementally.
  18.  
  19. The cost of building a Red-Black or AVL tree from an unsorted list is O(n log
  20. n). Thus a rebalancing operation on an existing binary tree should have a
  21. complexity no worse than a wholesale insertion of all of the elements of the
  22. tree into one of these data structures, else this method becomes more viable.
  23.  
  24. The incremental rebalancing operations in these algorithms add a O(log n) cost
  25. to an insertion or deletion operation, since the rebalancing operation requires
  26. that you look at only the nodes which dominate the newly inserted node.  If
  27. memory serves me, in the AVL algorithm, you look for a ``pivot'' node in the
  28. path that leads to the root node. You then do a rebalancing operation which
  29. involves checking a small number of cases. Since the search for the insertion
  30. point is O(log n) in the first place, the rebalancing adds nothing to the
  31. asymptotic cost of the insertion, other than worsen the coefficient.
  32.  
  33. >I wish there was an algorithms newsgroup, but it seems as if C/C++
  34. >programmers know better algorithms than just about anyone else.
  35.  
  36. There are other sources for research besides newsgroups. These kinds of basic
  37. algorithms are discussed in a myriad of computer science textbooks, papers,
  38. journals, etc. Though most of the papers would have to be pretty old for
  39. research about this particular topic!
  40.  
  41. >If you could send the code too, or just an algorithm description that 
  42. >would be great.  The important part is that it must be the fastest known so 
  43. >far.
  44.  
  45. I believe that a balanced tree can be constructed from a _sorted_ list in O(n),
  46. using a bottom-up algorithm. I doubt you could do it faster than this!
  47. -- 
  48.  
  49.